import java.util.Stack;

import jdk.internal.jshell.tool.resources.l10n;

/*
 * @lc app=leetcode.cn id=430 lang=java
 *
 * [430] 扁平化多级双向链表
 */

// @lc code=start

/*
// Definition for a Node.
class Node {
    public int val;
    public Node prev;
    public Node next;
    public Node child;
    public Node(int _val,Node _prev,Node _next,Node _child) {
        val = _val;
        prev = _prev;
        next = _next;
        child = _child;
    }
};
*/

class Solution {
    public Node flatten(Node head) {
        if(head == null){
            return head;
        }
        Node ans = new Node(0,null,head,null);
        Node curr, pre = ans;
        Stack<Node> stack = new Stack<>();
        stack.push(head);
        while(!stack.isEmpty()){
            curr = stack.pop();
            pre.next = curr;
            curr.prev = pre;
            if(curr.next != null){
                stack.push(curr.next);
            }
            if(curr.child != null){
                stack.push(curr.child);
                curr.child = null;
            }
            pre = curr;
        }
        ans.next.prev = null;
        return head;
    }
}
// @lc code=end

